Null graph

In the mathematical field of graph theory, the null graph may refer either to the order zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an empty graph).

Contents

Order zero graph

Order zero graph (null graph)
Vertices 0
Edges 0
Radius 0
Diameter 0
Girth \infty
Automorphisms 1
Chromatic number 0
Chromatic index 0
Genus 0
Properties Integral
Symmetric
Notation K_0

The order zero graph K_0 is the unique graph of order zero (having zero vertices). As a consequence, it also has zero edges. In some contexts, K_0 is excluded from being considered a graph (either by definition, or more simply as a matter of convenience).

The order zero graph is the initial object in the category of graphs, according to some definitions of a category of graphs. Its inclusion within the definition of graph theory is more useful in some contexts than others. On the positive side, K_0 follows naturally from the usual set-theoretic definitions of a graph (it is the ordered pair of empty sets), and in recursively defined data structures K_0 is useful for defining the base case for recursion (by treating the null tree as the child of missing edges in any non-null binary tree, every non-null binary tree has exactly two children). On the negative side, most well-defined formulas for graph properties must include exceptions for K_0 if it is included as a graph ("counting all strongly-connected components of a graph" would become "counting all non-null strongly-connected components of a graph"). Due to the undesirable aspects, it is usually assumed in literature that the term "graph" implies "graph with at least one vertex" unless context suggests otherwise.[1][2]

When acknowledged, K_0 fulfills (vacuously) most of the same basic graph properties as K_1 (the graph with one vertex and no edges): it has a size of zero, it is equal to its complement graph (\bar K_0), it is a connected component (namely, \forall x \isin V�: \forall y \isin V�: \exists path(x,y)), an acyclic graph, a tree, an arboricity, a forest, it may be an undirected graph or a directed graph (or even both), and it is both a complete graph and an empty graph (just to name a few). However, definitions for each of these graph properties will vary depending on whether context allows for K_0. For example, the term "connected component" almost always excludes K_0, whereas trees as data structures often include the "null tree" case.

Edgeless graph

Edgeless graph (empty graph, null graph)
Vertices n
Edges 0
Radius 0
Diameter 0
Girth \infty
Automorphisms n!
Chromatic number 1
Chromatic index 0
Genus 0
Properties Integral
Symmetric
Notation \bar K_n

For each natural number n, the edgeless graph (or empty graph) \bar K_n is the graph with n vertices and zero edges. An edgeless graph is occasionally referred to as a null graph in contexts where the order zero graph is not permitted.[3][4]

The n-vertex edgeless graph is the complement graph for the complete graph K_n, and therefore it is commonly denoted as \bar K_n.

See also

Notes

  1. ^ Weisstein, Eric W., "Empty Graph" from MathWorld.
  2. ^ Weisstein, Eric W., "Null Graph" from MathWorld.
  3. ^ Weisstein, Eric W., "Empty Graph" from MathWorld.
  4. ^ Weisstein, Eric W., "Null Graph" from MathWorld.

References